#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ret = 0;
        int dx[4] = { 0, 0, 1, -1 };
        int dy[4] = { 1, -1, 0, 0 };

        function<int(int, int)> dfs = [&](int r, int c)->int
            {
                int org = grid[r][c];
                grid[r][c] = 0;

                int maxPath = 0;
                for (int i = 0; i < 4; i++)
                {
                    int x = r + dx[i], y = c + dy[i];
                    if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y])
                        maxPath = max(maxPath, dfs(x, y));
                }
                grid[r][c] = org;
                return org + maxPath;
            };

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j]) ret = max(ret, dfs(i, j));

        return ret;
    }
};